/* $Id: linked_list_t.h 14 2010-11-18 21:56:36Z dheater@heatertech.com $ */

#ifndef __LINKED_LIST_H__
#define __LINKED_LIST_H__


namespace base
{
    /**
     * The linked list class is a simple template for creating a doubly linked
     * list data structure.
     * @param T The type of data in the linked list.
     */
    template<typename T>
        class linked_list_t
        {
            public:
                /**
                 * The structure of each node in the linked list.
                 */
                class node_t
                {
                    /**
                     * The owning class must be a friend in order to manipulate
                     * the list.
                     * @todo Need coding standard waiver for friend class.
                     */
                    friend class linked_list_t<T>;

                    public:
                    /**
                     * The data stored in the list.
                     */
                    T data;

                    /**
                     * Prefix increment operator.
                     * @return The next node in the list.
                     */
                    node_t* next()
                    {
                        return this->m_next;
                    }

                    node_t* prev()
                    {
                        return this->m_prev;
                    }

                    private:
                    /**
                     * A pointer to the previous node.
                     */
                    node_t* m_prev;

                    /**
                     * A pointer to the next node.
                     */
                    node_t* m_next;

                    /**
                     * Node constructor.
                     * @param t Node data.
                     * @param p Pointer to the previous node in the list.
                     * @param n Pointer to the next node in the list.
                     */
                    node_t(T t, node_t* p, node_t* n) :
                        data(t),
                        m_prev(p),
                        m_next(n)
                    {
                    }
                };

                /**
                 * Construct a queue, initialize as
                 * empty.
                 */
                linked_list_t() :
                    m_head(NULL),
                    m_tail(NULL)
            {
            }

                /**
                 * Get a pointer to the head of the list.
                 * @return Pointer to the head node.
                 */
                node_t* head() const
                {
                    return m_head;
                }

                /**
                 * Get a pointer to the tail of the list.
                 * @return Pointer to the tail node.
                 */
                node_t* tail() const
                {
                    return m_tail;
                }

                /**
                 * Put an element on the front of the list.
                 * @param t Data element to add the the list.
                 */
                void add_front(T t)
                {
                    m_head = new node_t(t, NULL, m_head);

                    if(m_head->m_next)
                    {
                        m_head->m_next->m_prev = m_head;
                    }

                    if(!m_tail)
                    {
                        m_tail = m_head;
                    }
                }

                /**
                 * Put an element on the tail of the list.
                 * @param t Data element to add the the list.
                 */
                void add_back(T t)
                {
                    m_tail = new node_t(t, m_tail, NULL);

                    if(m_tail->m_prev)
                    {
                        m_tail->m_prev->m_next = m_tail;
                    }

                    if(!m_head)
                    {
                        m_head = m_tail;
                    }
                }

                /**
                 * Remove an element from the front of the list.
                 */
                void delete_front()
                {
                    if(!m_head)
                    {
                        return;
                    }

                    node_t* temp(m_head);
                    m_head = m_head->m_next;

                    if(m_head)
                    {
                        m_head->m_prev = NULL;
                    }
                    else
                    {
                        m_tail = NULL;
                    }

                    delete temp;
                }

                /**
                 * Remove an element from the tail of the list.
                 * @param t Data element to add the the list.
                 */
                void delete_back()
                {
                    if(!m_tail)
                    {
                        return;
                    }

                    node_t* temp(m_tail);
                    m_tail = m_tail->m_prev;

                    if(m_tail)
                    {
                        m_tail->m_next = NULL;
                    }
                    else
                    {
                        m_head = NULL;
                    }

                    delete temp;
                }

            private:
                /**
                 * The first node in the list.
                 */
                node_t* m_head;

                /**
                 * The last node in the list.
                 */
                node_t* m_tail;
        };
}

#endif /* __LINKED_LIST_H__ */
